import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-16
 * Time: 16:47
 */
public class test_5 {

    public static void main(String[] args) {
        String a="abcbdb";
        String b="acbbabdbb";
        int m=a.length();
        int n=b.length();
        int[][] dp=new int[m+1][n+1];
        int i,j;
        for ( i = 0; i <=m; i++) {
            dp[i][0]=0;
        }
        for(j=0;j<=n;j++){
            dp[0][j]=0;
        }
        for (i=1;i<=m;i++){
            for (j=1;j<=n;j++){
                if (a.charAt(i-1)==b.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        int str_a=m;
        int str_b=n;
        int k=dp[m][n];
        char[] chars=new char[k];
        while (k>0){
            if (dp[str_a][str_b]==dp[str_a-1][str_b]){
                str_a--;
            }else if (dp[str_a][str_b]==dp[str_a][str_b-1]){
                str_b--;
            } else {
                chars[k-1]=a.charAt(str_a-1);
                k--;
                str_a--;
                str_b--;
            }
        }
        System.out.println(chars);
    }
}
